DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2022.70

Generalized Bundled Fragments for First-Order Modal Logic

Authors: Mo Liu, Anantha Padmanabha, R. Ramanujam, and Yanjing Wang

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract

When we bundle quantifiers and modalities together (as in ∃x□, ◇∀x etc.) in first-order modal logic (FOML), we get new logical operators whose combinations produce interesting bundled fragments of FOML. It is well-known that finding decidable fragments of FOML is hard, but existing work shows that certain bundled fragments are decidable [Anantha Padmanabha et al., 2018], without any restriction on the arity of predicates, the number of variables, or the modal scope. In this paper, we explore generalized bundles such as ∀x∀y□, ∀x∃y◇ etc., and map the terrain with regard to decidability, presenting both decidability and undecidability results. In particular, we propose the loosely bundled fragment, which is decidable over increasing domains and encompasses all known decidable bundled fragments.

Cite as

Mo Liu, Anantha Padmanabha, R. Ramanujam, and Yanjing Wang. Generalized Bundled Fragments for First-Order Modal Logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.MFCS.2022.70,
  author =	{Liu, Mo and Padmanabha, Anantha and Ramanujam, R. and Wang, Yanjing},
  title =	{{Generalized Bundled Fragments for First-Order Modal Logic}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.70},
  URN =		{urn:nbn:de:0030-drops-168684},
  doi =		{10.4230/LIPIcs.MFCS.2022.70},
  annote =	{Keywords: bundled fragments, first-order modal logic, decidability, tableaux}
}

Search Results

Documents authored by Liu, Mo

Generalized Bundled Fragments for First-Order Modal Logic

Abstract

Cite as

Thanks for your feedback!

Could not send message